// DC6651.cpp : Defines the entry point for the console application.
//
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <list>
#include <algorithm>
#include <assert.h>
#include <vector>
using namespace std;

#define MAX_OBJECT 1000

int nStrip;
int nObject;
FILE* fout;

struct OBJECT
{
	float width;
	float height;
	int strip;
	float x; // the x coordinate where we put the object
	float y; // the y coordinate where we put the object
} object_list[MAX_OBJECT];

struct STEP // a step in skyline
{
	float width;
	float height;
};

struct STRIP
{
	list < STEP> step_list;
	float max_height;
	list < int> object_list; // List of object in the trip
	int id;
};

#define STRIP_LIST vector < STRIP>

bool ReadData(const char* lpszFileName)
{
	FILE* f = fopen(lpszFileName, "rt");
	
	if (f == NULL)
		return false;
	
	fscanf(f, "%d", &nStrip);
	fscanf(f, "%d", &nObject);
	float w, h;
	
	for (int i = 0; i < nObject; i++)
	{
		fscanf(f, "%f", &w);
		fscanf(f, "%f", &h);
		object_list[i].width = w;
		object_list[i].height = h;
	}
	
	fclose(f);
	return true;
}

void Error(const char* lpszErrorMsg)
{
	fprintf(fout, lpszErrorMsg);
	fprintf(fout, "\n");
	exit(0);
}

struct  RECT
{
    float    left;
    float    top;
    float    right;
    float    bottom;
}; 

bool IntersectRect(RECT& r1, RECT& r2)
{
    return !(r2.left > r1.right
        || r2.right < r1.left
        || r2.top > r1.bottom
        || r2.bottom < r1.top
		);
}

bool CheckResult(STRIP_LIST& strip_list)
{
	RECT list_rect[MAX_OBJECT];
	list < int>::iterator j;
	int k;
	float max_h;
	int m, n;
	
	for (int i = 0; i < strip_list.size(); i++)
	{
		k = 0;
		max_h = 0;
		
		for (j = strip_list[i].object_list.begin(); j != strip_list[i].object_list.end(); j++) 
		{
			OBJECT& obj = object_list[*j];
			list_rect[k].left = obj.x;
			list_rect[k].right = obj.x + obj.width;
			list_rect[k].bottom = obj.y;
			list_rect[k].top = obj.y + obj.height;
			
			if (list_rect[k].top >max_h)
				max_h = list_rect[k].top;
			
			k++;
		}
		
		
		if (max_h != strip_list[i].max_height)
			return false;
		
		
		for (m = 0; m < k - 1; m++)
			for (n = m + 1; n < k; n++) 
			{
				if (IntersectRect(list_rect[m], list_rect[n]))
					return false;
			}
	}
	
	return true;
}

void PrintStepList(STRIP& strip)
{
	list < STEP>::iterator j;
	
	fprintf(fout, "Skyline %d: ", strip.id);
	
	for (j = strip.step_list.begin(); j != strip.step_list.end(); j++) 
		fprintf(fout, "(%f,%f) ", (*j).width, (*j).height);
	
	fprintf(fout, "\n");
}

void PrintStepList(STRIP_LIST& strip_list)
{
	for (int i = 0; i < strip_list.size(); i++)
		PrintStepList(strip_list[i]);
	
	fprintf(fout, "\n");
}

void PrintStrip(STRIP& strip)
{
	fprintf(fout, "Strip%d, height=%.2f:\n", strip.id + 1, strip.max_height);
	
	list < int>::iterator j;
	
	for (j = strip.object_list.begin(); j != strip.object_list.end(); j++) 
	{
		OBJECT& obj = object_list[*j];
		fprintf(fout, "Object%d(%.2f,%.2f) ", (*j) + 1, obj.x, obj.y);
	}
	
	fprintf(fout, "\n");
}

void PrintStripList(STRIP_LIST& strip_list)
{
	for (int i = 0; i < strip_list.size(); i++)
		PrintStrip(strip_list[i]);
	
	fprintf(fout, "\n");
}

void PrintResult(STRIP_LIST& strip_list)
{
	int i;
	float max_height = 0;
	
	for (i = 0; i < strip_list.size(); i++)
	{
		PrintStrip(strip_list[i]);
		
		if (strip_list[i].max_height > max_height)
			max_height = strip_list[i].max_height;
		fprintf(fout, "\n");
	}
	
	fprintf(fout, "Max height: %.2f\n", max_height);
}

// Merge strip1 to strip2
void MergeStrip(STRIP& strip1, STRIP& strip2)
{
	list < int>::iterator it;
	list < STEP>::iterator it2;
	float top = strip2.max_height;
	
	for (it = strip1.object_list.end(); it != strip1.object_list.begin(); )
	{
		it--;
		OBJECT& obj = object_list[*it];
		obj.strip = strip2.id; // put this object to strip 2;
		
		// modify the skyline of the strip 2		
		// Find the first step in the skyline which interferes with this object (horizontally)
		it2 = strip2.step_list.begin();
		float temp = 0;
		
		while (true) 
		{
			temp = temp +(*it2).width;
			
			if (temp> obj.x)
				break; // must happen somewhere
			else
			{
				it2++;
			}
		}
		
		// Check if the left side of this step is aligned with the left side of the object
		// and the right side of this step is aligned with the right side of the object
		// if this is the case, then we do not need to insert a new step
		// just replace this step
		// |-------|
		// |-------|
		if (((*it2).width == obj.width) &&
			(temp == obj.x + obj.width))
		{
			obj.y = it2->height;
			it2->height += obj.height;
			
			if (it2->height > top)
				top = it2->height;
		}
		else 
			//    |-------|
			// |----------|
			if (temp == obj.x + obj.width)
			{// resize this step and create a new step here
				obj.y = it2->height;
				it2->width -= obj.width;
				
				STEP step;
				step.width = obj.width;
				step.height = it2->height + obj.height;
				
				if (step.height > top)
					top = step.height;
				
				it2++;
				strip2.step_list.insert(it2, step);
			}
			else
				//  |--------|
				//  |-----------|
				if (((*it2).width > obj.width) &&
					(temp == obj.x +(*it2).width))
				{// create a new step and resize this step
					obj.y = it2->height;
					it2->width -= obj.width;
					
					STEP step;
					step.width = obj.width;
					step.height = it2->height + obj.height;
					
					if (step.height > top)
						top = step.height;
					
					strip2.step_list.insert(it2, step);
					it2++;
				}
				else
					//     |------|
					//  |-----------|
					if (obj.x + obj.width < temp)
					{// resize this step and create two new steps here
						obj.y = it2->height;
						it2->width = obj.x -(temp - it2->width);
						
						STEP step;
						step.width = obj.width;
						step.height = it2->height + obj.height;
						
						if (step.height > top)
							top = step.height;
						
						it2++;
						strip2.step_list.insert(it2, step);
						
						step.width = temp -(obj.x +obj.width);
						step.height = it2->height;
						strip2.step_list.insert(it2, step);
					}
					else
						//      |--------------|
						//  |-----------|
						if ((temp -(*it2).width < obj.x)&&
							(temp < obj.x + obj.width))
						{// resize this step and create a new step here
							obj.y = it2->height;
							it2->width = obj.x + (*it2).width - temp;
							
							STEP step;
							step.width = obj.width;
							step.height = it2->height + obj.height;
							
							if (step.height > top)
								top = step.height;
							
							it2++;
							strip2.step_list.insert(it2, step);
						}
						else
							//  |--------------|
							//  |-----------|
							if ((temp -(*it2).width == obj.x)&&
								(temp < obj.x + obj.width))
							{// change this step
								obj.y = it2->height;
								it2->width = obj.width;
								it2->height += obj.height;
								
								if (it2->height > top)
									top = it2->height;			
								it2++;
							}
							
							if ((temp < obj.x + obj.width))
							{
								// remove the steps that are "below" the new step
								while (it2 != strip2.step_list.end())
								{
									if (temp >= obj.x + obj.width)
										break;
									
									temp += it2->width;
									
									if (temp <= obj.x + obj.width) 
									{// remove this step since it's completely under the object
										it2 = strip2.step_list.erase(it2);
									}
									else
									{// not completely under the object => narrow down this 
										it2->width = temp - obj.x - obj.width;
										break;
									}
								}
							}
							
							strip2.max_height = top;
							strip2.object_list.push_back(*it);
	}
}

bool compare1(const STRIP& a, const STRIP& b)
{
	return (a.max_height > b.max_height);
}

bool compare2(const STRIP& a, const STRIP& b)
{
	return (a.max_height < b.max_height);
}
void DevideAndConquer(int first_object, int last_object, STRIP_LIST& strip_list)
{
	// First we need to check if this is a trivial case
	// that is we can put all these objects to on self
	int i = first_object;
	int j = 0;
	bool trivial = true;
	float total_width = 0;
	
	while (i <= last_object)
	{
		total_width += object_list[i].width;
		
		if (total_width > 1)
		{
			i--;
			total_width = 0;
			j++;
			
			if (j > nStrip - 1)
			{
				trivial = false;
				break;
			}
		}
		else
			i++;
	}
	
	STEP step;
	float max_height;	
	
	if (trivial)
	{	
		i = first_object;
		j = 0;
		total_width = 0;
		max_height = 0;
		
		while (i <= last_object)
		{
			total_width += object_list[i].width;
			
			if (total_width == 1)
			{
				object_list[i].x = 1 - object_list[i].width;
				object_list[i].y = 0;
				
				strip_list[j].object_list.push_back(i);
				step.width = object_list[i].width;
				step.height = object_list[i].height;
				strip_list[j].step_list.push_back(step);
				
				if (max_height < step.height)
					max_height = step.height;
				
				strip_list[j].max_height = max_height;
				
				max_height = 0;
				total_width = 0;
				i++;
				j++;
			}
			else
				if (total_width < 1)
				{
					object_list[i].x = total_width - object_list[i].width;
					object_list[i].y = 0;
					
					strip_list[j].object_list.push_back(i);
					step.width = object_list[i].width;
					step.height = object_list[i].height;
					strip_list[j].step_list.push_back(step);
					
					if (max_height < step.height)
						max_height = step.height;
					
					i++;
				}
				else // > 1
				{
					step.width = 1 + object_list[i].width - total_width;
					step.height = 0;
					strip_list[j].step_list.push_back(step);
					strip_list[j].max_height = max_height;
					
					max_height = 0;
					total_width = 0;
					j++;
				}
		}
		
		while (j < nStrip)
		{// insert the last step with height 0
			step.width = 1 - total_width;
			step.height = 0;
			strip_list[j].step_list.push_back(step);
			strip_list[j].max_height = max_height;
			j++;
			total_width = 0; // so that the spared strips are covered by 0 skyline
			max_height = 0;
		}
		return; // trivial == true;
	}
	
	// trivial == false
	// divide this by two
	int middle =(first_object + last_object)/2;
	
	STRIP_LIST strip_list1, strip_list2;
	STRIP st;
	st.max_height = 0;
	
	for (i = 0; i < nStrip; i++)
	{
		st.id = i;	
		strip_list1.push_back(st);
		strip_list2.push_back(st);
	}
	
	DevideAndConquer(first_object, middle, strip_list1);
	DevideAndConquer(middle + 1, last_object, strip_list2);
	
	sort(strip_list1.begin(), strip_list1.end(), compare1);
	sort(strip_list2.begin(), strip_list2.end(), compare2);
	
	for (i = 0; i < strip_list1.size(); i++)
	{
		MergeStrip(strip_list1[i], strip_list2[i]);
	}
	
	strip_list = strip_list2;
}

int main(int argc, char* argv[])
{
	if (argc <= 1)
	{
		printf("No input data!\n");
		return 0;
	}

	if (argc == 3) // log file result
	{
		fout = fopen(argv[2], "wt");
		
		if (fout == NULL)
		{
			fprintf(fout, "Cannot write result to file, using screen instead!\n");
			fout = stdout;
		}
	}
	else
		fout = stdout;

	if (!ReadData(argv[1]))
	{
		fprintf(fout, "Error reading data!\n");
		return 0;
	}
	

	
	fprintf(fout, "Begin Device and Conquer...\n");
	clock_t start_time = clock();
	
	STRIP_LIST strip_list;
	
	int i;
	STRIP st;
	st.max_height = 0;
	
	for (i = 0; i < nStrip; i++)
	{
		st.id = i;	
		strip_list.push_back(st);
	}
	
	DevideAndConquer(0, nObject - 1, strip_list);
	
	PrintResult(strip_list);
	
	clock_t running_time;
	running_time = clock();
	
	fprintf(fout, "Running time: %f s\n", double(running_time - start_time)/CLOCKS_PER_SEC);
	
	fprintf(fout, "Checking result...\n");
	
	if (CheckResult(strip_list))
		fprintf(fout, "OK!\n");
	else
		fprintf(fout, "Error!\n");
	
	if (argc == 3)
		fclose(fout);
	
	return 0;
}
